package com.mzy.linear_struct.ks.回溯;

import java.util.*;

/**
 * @Author: mizy3
 * @Date: 2024/08/24/上午3:02
 * @Description:
 */
public class 字母组合 {

    /*
    public List<String> permute(String str) {

        char[] strs = str.toCharArray();

        Deque<Character> path = new LinkedList<>();
        List<String> ans = new ArrayList<>();
        boolean[] used = new boolean[str.length()];
        backtracking(strs, path, 0, used, ans);
        return ans;

    }

    private void backtracking(char[] strs, Deque<Character> path, int depth, boolean[] used, List<String> ans) {
        if (depth == strs.length) {
            StringBuilder builder = new StringBuilder();
            path.forEach(builder::append);
            ans.add(builder.toString());
            return;
        }

        for (int i = 0; i < strs.length; i++) {
            if (used[i]) {
                continue;
            }
            if(i > 0 && strs[i] == strs[i - 1] && used[i - 1]) continue;
            path.addLast(strs[i]);
            used[i] = true;
            backtracking(strs, path, depth + 1, used, ans);
            used[i] = false;
            path.removeLast();
        }

    }
    */

    public static void main(String[] args) {
        List<String> ans = new 字母组合().permute("abb");
        // abb abb bab bba bab bba
        System.out.println(ans);
    }

    private List<String> permute(String str) {

        StringBuilder path = new StringBuilder();
        List<String> ans = new ArrayList<>();
        boolean[] used = new boolean[str.length()];
        dfs(str, path, used,  ans);
        return ans;
    }

    private void dfs(String str, StringBuilder path,boolean[] used,  List<String> ans) {
        if (path.length() == str.length()) {
            ans.add(path.toString());
            return;
        }

        for(int i = 0; i < str.length(); i++){
            if(i > 0 && str.charAt(i - 1) == str.charAt(i) && used[i - 1]){
                continue;
            }
            if(!used[i]){
                path.append(str.charAt(i));
                used[i] = true;
                dfs(str, path, used, ans);
                path.deleteCharAt(path.length() - 1);
                used[i] = false;
            }
        }
    }
}



















